import java.util.ArrayList;
import java.util.List;

class Solution {
    private int n;
    private int solutionCount;

    public int getSize(int n) {
        this.n = n;
        this.solutionCount = 0;
        backtrack(0, 0, 0, 0);
        return solutionCount;
    }

    private void backtrack(int row, int colMask, int diag1Mask, int diag2Mask) {
        if (row == n) {
            solutionCount++;
            return;
        }

        // 计算可用列（二进制中1表示可用）
        int availablePositions = ((1 << n) - 1) & ~(colMask | diag1Mask | diag2Mask);

        while (availablePositions != 0) {
            // 获取最低位的1（即下一个可用列）
            int position = availablePositions & -availablePositions;

            // 递归处理下一行
            backtrack(
                    row + 1,
                    colMask | position,
                    (diag1Mask | position) << 1,
                    (diag2Mask | position) >> 1
            );

            // 清除最低位的1，继续处理下一个可用列
            availablePositions &= availablePositions - 1;
        }
    }
}

class SolutionMain {
    public static void main(String[] args) {
        long stime = System.currentTimeMillis();

        List<Integer> list1 = new ArrayList<>();
        Solution solution = new Solution();
        int maxN = 15;

        for (int i = 0; i < maxN; i++) {
            list1.add(solution.getSize(i));
        }

        System.out.printf("%d次 SIZE数值：%d   \n", maxN, list1.get(list1.size() - 1));
        long etime = System.currentTimeMillis();
        System.out.printf("执行时长：%d 毫秒.", (etime - stime));
    }
}